home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 168_01 / srt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-08-19  |  8.5 KB  |  335 lines
  1. /* SDB - sort routines */
  2.  
  3. #include "stdio.h"
  4. #include "sdbio.h"
  5.  
  6. extern int dbv_token;
  7. extern char dbv_tstring[];
  8. extern int dbv_tvalue;
  9.  
  10. /* get_skeys - get sort key list */
  11. static struct skey *get_skeys(sptr)
  12.   struct scan *sptr;
  13. {
  14.     struct skey *skeys,*newskey,*lastskey;
  15.  
  16.     /* parse a list of attribute names */
  17.     skeys = lastskey = NULL;
  18.     while (TRUE) {
  19.  
  20.         /* get attribute name */
  21.         if (db_ntoken() != ID)
  22.             return (db_nerror(SYNTAX));
  23.  
  24.         /* allocate a sort key structure */
  25.         if ((newskey = malloc(sizeof(struct skey))) == NULL)
  26.             return (db_nerror(INSMEM));
  27.  
  28.         /* initialize the sort key structure */
  29.         newskey->sk_next = NULL;
  30.  
  31.         /* lookup the attribute name */
  32.         if (!find_attr(sptr,newskey,dbv_tstring)) {
  33.             free(newskey);
  34.             return (NULL);
  35.         }
  36.  
  37.         /* check for ascending or descending */
  38.         if (db_token() == ASCENDING || dbv_token == DESCENDING) {
  39.             newskey->sk_type = dbv_token;
  40.             db_ntoken();
  41.         }
  42.         else
  43.             newskey->sk_type = ASCENDING;
  44.  
  45.         /* link the sort key structure into the list */
  46.         if (lastskey == NULL)
  47.             skeys = newskey;
  48.         else
  49.             lastskey->sk_next = newskey;
  50.         lastskey = newskey;
  51.  
  52.         /* check for more attributes */
  53.         if (db_token() != ',')
  54.             break;
  55.         db_ntoken();
  56.     }
  57.  
  58.     /* return successfully */
  59.     return (skeys);
  60. }
  61.  
  62. /* db_sort - sort tuples in a relation */
  63. int *db_sort(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9)
  64.   char *fmt;
  65. {
  66.     struct scan *sptr1,*sptr2,*sptr3;   /*dns*/
  67.     struct skey *skeys;
  68.     int result;
  69.  
  70.     /* check for a command line */
  71.     if (fmt != NULL)
  72.         db_scan(fmt,a1,a2,a3,a4,a5,a6,a7,a8,a9);
  73.  
  74.     /* checks for relation name */
  75.     if (db_token() == ID)
  76.         db_ntoken();
  77.     else
  78.         strcpy(dbv_tstring,"sdbcur");
  79.  
  80.     /* open the relation */
  81.     if ((sptr1 = db_ropen(dbv_tstring)) == NULL)
  82.         return (FALSE);
  83.     if ((sptr2 = db_ropen(dbv_tstring)) == NULL) {
  84.         db_rclose(sptr1);
  85.         return (FALSE);
  86.         }
  87.     if ((sptr3 = db_ropen(dbv_tstring)) == NULL) {   /*dns*/
  88.         db_rclose(sptr1);                            /*dns*/
  89.         db_rclose(sptr2);                            /*dns*/
  90.         return (FALSE);                              /*dns*/
  91.         }
  92.  
  93.     /* checks for "<relation-name> by <sort-list>" */
  94.     if (db_ntoken() != BY)
  95.         return (db_ferror(SYNTAX));
  96.     if ((skeys = get_skeys(sptr1)) == NULL) {
  97.         db_rclose(sptr1);
  98.         db_rclose(sptr2);
  99.         db_rclose(sptr3);  /*dns*/
  100.         return (FALSE);
  101.        }
  102.  
  103.     /* do the sort */
  104.     result = sort(skeys,sptr1,sptr2,sptr3);  /*dns*/
  105.  
  106.     /* close the relation */
  107.     db_rclose(sptr1);
  108.     db_rclose(sptr2);
  109.     db_rclose(sptr3);     /*dns*/
  110.  
  111.     /* free the sort keys */
  112.     free_skeys(skeys);
  113.  
  114.     return (result);
  115. }
  116.  
  117. /* free_skeys - free a list of sort keys */
  118. static free_skeys(skeys)
  119.   struct skey *skeys;
  120. {
  121.     struct skey *thisskey;
  122.  
  123.     for (thisskey = skeys; skeys != NULL; thisskey = skeys) {
  124.         skeys = skeys->sk_next;
  125.         free(thisskey);
  126.     }
  127. }
  128.  
  129. /* find_attr - find an attribute */
  130. static int find_attr(sptr,newskey,aname)
  131.   struct scan *sptr; struct skey *newskey; char *aname;
  132. {
  133.     struct attribute *aptr;
  134.     int i,astart;
  135.  
  136.     /* loop through each attribute within the relation */
  137.     astart = 1;
  138.     for (i = 0; i < NATTRS; i++) {
  139.  
  140.         /* get a pointer to the current attribute */
  141.         aptr = &sptr->sc_relation->rl_header.hd_attrs[i];
  142.  
  143.         /* check for last attribute */
  144.         if (aptr->at_name[0] == 0)
  145.             break;
  146.  
  147.         /* check for attribute name match */
  148.         if (db_sncmp(aname,aptr->at_name,ANSIZE) == 0) {
  149.             newskey->sk_start = astart;
  150.             newskey->sk_aptr = aptr;
  151.             return (TRUE);
  152.         }
  153.  
  154.         /* update the attribute start */
  155.         astart += aptr->at_size;
  156.     }
  157.  
  158.     /* attribute name not found */
  159.     return (db_ferror(ATUNDF));
  160. }
  161.  
  162. /* sort - sort the relation */
  163. static int sort(skeys,sptr1,sptr2,sptr3)
  164.   struct skey *skeys; struct scan *sptr1,*sptr2,*sptr3;
  165. {
  166. /*  unsigned int j,k,l,r;          dns */
  167.     long int passes,swaps;           /*dns*/
  168.     int i, j, m, n;         /*dns*/
  169.     int rec1 = 0;           /*dns*/
  170.     int rec2 = 0;           /*dns*/
  171.     int rec3 = 0;           /*dns*/
  172.     int dns = 0;            /*dns*/
  173.     FILE *test;             /*dns*/
  174.  
  175.     passes = 0L;
  176.     swaps = 0L;
  177.  
  178.     /*dns --->   */
  179.     test = fopen("sort.dat", "w");
  180.     n = sptr1->sc_relation->rl_tcnt;
  181.     m = n;
  182.  
  183.     while( m>1 )   {
  184.        passes++;
  185.        if ((m/=3.14159) < 1)  m = 1;
  186.        for ( j=1; j<=n-m; j++ )  {
  187.           if( rec1 != j+m )  {
  188.              if(dns) fprintf(test,"Read1: %d\n", j+m);
  189.              if (!db_rget(sptr1, rec1=j+m))  return (FALSE);
  190.              }
  191.           for ( i=j; i>=1; i-=m ) {
  192.              if( rec2 != i )   {
  193.                 if(dns) fprintf(test,"Read2: %d\n", i);
  194.                 if (!db_rget(sptr2, rec2=i))  return (FALSE);
  195.                 }
  196.              if (compare(skeys,sptr1,sptr2) > 0)
  197.                 break;
  198.              if(rec3 != i+m)  {
  199.                 if(dns) fprintf(test,"Read3: %d\n", i+m);
  200.                 if (!db_rget(sptr3, rec3=i+m))  return (FALSE);
  201.                 }
  202.              if(dns) fprintf(test,"Write 3,2: %d from %d\n", i+m, i);
  203.              assign( sptr3, sptr2 );
  204.              swaps++;
  205.              }
  206.           if(rec1 != i+m)  {
  207.              if(rec3 != i+m)  {
  208.                 if(dns) fprintf(test,"Read 3: %d\n", i+m);
  209.                 if (!db_rget(sptr3, rec3=i+m))  return (FALSE);
  210.                 }
  211.              if(dns) fprintf(test,"Write 3,1: %d from %d\n", i+m, j+m);
  212.              assign( sptr3, sptr1 );
  213.              swaps++;
  214.              }
  215.           }
  216.        }
  217.        fclose(test);
  218.  
  219. /*
  220.     l = 2;
  221.     r = sptr1->sc_relation->rl_tcnt;
  222.     k = r;
  223.  
  224.     do {
  225.         for (j = r; j >= l; j--) {
  226.             if (!db_rget(sptr1,j-1))
  227.                 return (FALSE);
  228.             if (!db_rget(sptr2,j))
  229.                 return (FALSE);
  230.             if (compare(skeys,sptr1,sptr2) > 0) {
  231.                 swap(sptr1,sptr2);
  232.                 k = j;
  233.                 swaps++;
  234.             }
  235.         }
  236.         l = k + 1;
  237.         for (j = l; j <= r; j++) {
  238.             if (!db_rget(sptr1,j-1))
  239.                 return (FALSE);
  240.             if (!db_rget(sptr2,j))
  241.                 return (FALSE);
  242.             if (compare(skeys,sptr1,sptr2) > 0) {
  243.                 swap(sptr1,sptr2);
  244.                 k = j;
  245.                 swaps++;
  246.             }
  247.         }
  248.         r = k - 1;
  249.         passes++;
  250.     } while (l <= r);
  251. */
  252.  
  253.     printf("[ Passes: %ld  Swaps: %ld ]\n",passes,swaps);
  254.  
  255.     return (TRUE);
  256. }
  257.  
  258. /* compare - compare two tuples */
  259. static int compare(skeys,sptr1,sptr2)
  260.   struct skey *skeys; struct scan *sptr1,*sptr2;
  261. {
  262.     struct skey *cskey;
  263.     int result;
  264.  
  265.     for (cskey = skeys; cskey != NULL; cskey = cskey->sk_next)
  266.         if ((result = cattr(cskey,sptr1,sptr2)) != 0)
  267.             break;
  268.  
  269.     return (result);
  270. }
  271.  
  272. /* cattr - compare two attributes */
  273. static int cattr(cskey,sptr1,sptr2)
  274.   struct skey *cskey; struct scan *sptr1,*sptr2;
  275. {
  276.     int astart,aend,i;
  277.  
  278.     astart = cskey->sk_start;
  279.     aend = astart + cskey->sk_aptr->at_size;
  280.  
  281.     for (i = astart; i < aend; i++)
  282.         if (sptr1->sc_tuple[i] != sptr2->sc_tuple[i])
  283.             break;
  284.  
  285.     if (i == aend)
  286.         return (0);
  287.  
  288.     if (sptr1->sc_tuple[i] < sptr2->sc_tuple[i])
  289.         if (cskey->sk_type == ASCENDING)
  290.             return (-1);
  291.         else
  292.             return (1);
  293.     else
  294.         if (cskey->sk_type == ASCENDING)
  295.             return (1);
  296.         else
  297.             return (-1);
  298. }
  299.  
  300. /* swap - swap two tuples */
  301. /* dns
  302. static int swap(sptr1,sptr2)
  303.   struct scan *sptr1,*sptr2;
  304. {
  305.     unsigned int tnum1,tnum2;
  306.  
  307.     tnum1 = sptr1->sc_atnum;
  308.     tnum2 = sptr2->sc_atnum;
  309.  
  310.     if (!db_rput(sptr1,tnum2))
  311.         return (FALSE);
  312.     if (!db_rput(sptr2,tnum1))
  313.         return (FALSE);
  314.  
  315.     return (TRUE);
  316. }
  317.   dns  */
  318.  
  319.  
  320. /* assign - assign one tupple to another */
  321. static int assign(sptr1,sptr2)
  322.   struct scan *sptr1,*sptr2;
  323. {
  324.     unsigned int tnum1,tnum2;
  325.  
  326.     tnum1 = sptr1->sc_atnum;
  327.  
  328.     if (!db_rput(sptr2,tnum1))
  329.         return (FALSE);
  330.  
  331.     return (TRUE);
  332. }
  333.  
  334. tr->sa_aname = malloc(strlen(dbv_tstring)+1)) == NULL) {
  335.             free(newsa